package leetcode.code0873;

public class Solution1 extends Solution873 {


	@Override
	public int lenLongestFibSubseq(int[] arr) {
		int n = arr.length;
		int max = 0;
		int[][] dp = new int[n][n];
		for (int end = 2; end < n; end++) {
			int L = 0, R = end - 1;
			while (L < R) {
				if (arr[L] + arr[R] == arr[end]) {
					if (dp[L][R] == 0) {
//						dp[L][R] = 2;
						dp[R][end] = 3;
					} else {
						dp[R][end] = dp[L][R] + 1;
					}
					max = Math.max(max, dp[R][end]);
					L++;
					R--;
				} else if (arr[L] + arr[R] < arr[end]) {
					L++;
				} else {
					R--;
				}
			}
		}
		return max;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
